#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll f(ll x){
  ll y=--x>>1;
  return (ll)x*(x+1)/2-(ll)y*(y+1)-(x&1?y+1:0);
}
int main(){
  freopen("tree.in","r",stdin);
  freopen("tree.out","w",stdout);
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    ll s,l=0,r=2.1e9; cin>>s;
    if(!s){cout<<"2\n"; continue;}
    while(l<r){
      ll m=l+r>>1;
      if(f(m)>=s)r=m;
      else l=m+1;
    }
    cout<<(r|(f(r)^s)&1)<<'\n';
  }
  return 0;
}